package features.advance.leetcode.linkedlist.easy;

import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.util.TreeUtil;

/**
 *  剑指 Offer 24. 反转链表
 *
 *  难度：简单
 *
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 *
 *
 * 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/
 *
 * @author LIN
 * @date 2021-06-17
 */
public class Offer24 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            /**
             * 递归
             * 递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，、
             * 现在应该如何反转它前面的部分？
             *
             * 假设链表为：
             * n1 -> ... -> nk-1 -> nk -> nk+1 -> ... -> nm -> ∅
             * 若从节点nk+1到nm已经被反转，而我们正处于nk
             *
             * 我们希望nk+1的下一个节点指向nk
             * n1 -> ... -> nk-1 -> nk -> nk+1 <- ... <- nm
             * 所以nk.next.next=nk
             * 需要注意的是 n1的下一个节点必须指向∅。如果忽略了这一点，链表中可能会产生环。
             * @param head
             * @return
             */
            @Override
            public ListNode reverseList(ListNode head) {
                if (head == null || head.next == null) {
                    return head;
                }
                ListNode newHead = reverseList(head.next);
                head.next.next = head;
                // head 和 head.next 会相互指向，形成环
                head.next = null;
                return newHead;
            }
        };
        String str = "[1,2,3,4,5]";
        ListNode head = TreeUtil.parseLinkedList(str);
        ListNode listNode = solution.reverseList(head);
        System.out.println(listNode);
    }

    static class Solution {
        /**
         * 反转链表，双指针
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            if(head == null){
                return null;
            }
            // 初始值必须是null，表示最后一个节点指向null
            ListNode pre = null;
            ListNode cur = head;
            while(cur!=null){
                System.out.println(cur.val);
                // 下一个节点
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                // 移动到下一个节点
                cur = next;
            }
            return pre;
        }
    }
}
